package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * LC105.从前序与中序遍历序列构造二叉树
 */
public class LC105 {
    private Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart >= preEnd) {
            return null;
        }
        int rootVal = preorder[preStart];
        Integer rootIndex = map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        int leftLen = rootIndex - inStart;
        root.left = build(preorder, preStart + 1, preStart + 1 + leftLen, inorder, inStart, rootIndex);
        root.right = build(preorder, preStart + leftLen + 1, preEnd, inorder, rootIndex + 1, inEnd);
        return root;
    }

    public static void main(String[] args) {
        LC105 alg = new LC105();
        int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        TreeNode treeNode = alg.buildTree(preorder, inorder);
        System.out.println(treeNode);
    }
}
